BZOJ 1572 工作安排Job

Description

Farmer John 有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。 他的工作日从0时刻开始,有1000000000个单位时间(!)。在任一时刻,他都可以选择编号1~N的N(1 <= N <= 100000)项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有N个工作,虽然还是有可能。 对于第i个工作,有一个截止时间D_i(1 <= D_i <= 1000000000),如果他可以完成这个工作,那么他可以获利P_i( 1<=P_i<=1000000000 ). 在给定的工作利润和截止时间下,FJ能够获得的利润最大为多少呢?答案可能会超过32位整型。

Input

第1行:一个整数N. 第2~N+1行:第i+1行有两个用空格分开的整数:D_i和P_i.

Output

输出一行,里面有一个整数,表示最大获利值。

Sample Input

3
2 10
1 5
1 7

Sample Output

17

Hint

第1个单位时间完成第3个工作(1,7),然后在第2个单位时间完成第1个工作(2,10)以达到最大利润

Solution

先能选就选,不能再放弃个最差的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct tasks{
int d,p;
}task[maxn];

priority_queue<int,vector<int>,greater<int> > q;
ll ans;
int n,line;

bool comp(tasks a,tasks b)
{

return a.d<b.d;
}

void sovle()
{

for(int i=1;i<=n;i++)
if( line<task[i].d ){
q.push(task[i].p);
ans+=task[i].p,line++;
}
else if( task[i].p>q.top() ){
ans+=task[i].p-q.top();
q.push(task[i].p),q.pop();
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1572.in","r",stdin);
freopen("1572.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&task[i].d,&task[i].p);
sort(task+1,task+n+1,comp);
sovle();
printf("%lld",ans);
return 0;
}